﻿namespace Leetcode.N0124;
public class Solution
{
    public int MaxPathSum(TreeNode root)
    {
        var ans = this.MaxPathSumNode(root);
        return ans.rootSum;
    }

    private (int pathSum, int rootSum) MaxPathSumNode(TreeNode node)
    {
        if (node == null)
        {
            return (int.MinValue, int.MinValue);
        }

        var left = this.MaxPathSumNode(node.left);
        var right = this.MaxPathSumNode(node.right);
        var pathSum = node.val;
        if (left.pathSum > 0)
        {
            pathSum = Math.Max(left.pathSum + pathSum, right.pathSum > 0 ? right.pathSum + pathSum : pathSum);
        }
        else
        {
            pathSum = right.pathSum > 0 ? pathSum + right.pathSum : pathSum;
        }

        var rootSum = node.val + (left.pathSum > 0 ? left.pathSum : 0) + (right.pathSum > 0 ? right.pathSum : 0);

        rootSum = Math.Max(Math.Max(rootSum, left.rootSum), right.rootSum);
        return (pathSum, rootSum);
    }
}
